﻿#include "stdafx.h"
#include "FuncGetLoops.h"

UINT32 g_idSeg = 0;
UINT32 g_idChildSeg = 0;

FuncGetLoops* g_Func = NULL;

// 代码调用层次

// init
// AppendSeg
// DoFindLoop
//   GetAllSegsInterPoint
//     IsSegVer                             交点到起点的距离使用
//     GeMathPublic::isSegInterSeg          计算交点
//     AddInterPointToSeg                      添加交点信息
//     ClearSingleSeg                          清理胡子
//       IsSegSingleByJoinedSegs                   判断是否是胡子
//       AppendChildSegsFromSeg                    离散 非胡子原始线段
//         SortSegInterPoints
//   GetAllIntLoops
//     GetNoClosedMiniSeg
//     GetLoopFromStartMiniSeg
//       GetNextMiniSeg
//         GetTurnRightAng
//       SetLoopSegsHalfSide
// GetResultAndClose

FuncGetLoops::FuncGetLoops()
{
	g_idSeg = 0;
	g_idChildSeg = 0;

	m_idToSegMap.clear();
	m_idToSMiniSegMap.clear();

	m_Segs.clear();
	m_ChildSegs.clear();

	m_intLoops.clear();
	m_outLoops.clear();
}

FuncGetLoops::~FuncGetLoops()
{
}

void FuncGetLoops::Init()
{
	g_Func = new FuncGetLoops();
}

// 1， 搜集数据
void FuncGetLoops::AppendSeg(DPoint3d ps, DPoint3d pe)
{
	// 重复线段处理，暂时先不做
	g_idSeg++;
	LineSegForLoop* seg = new LineSegForLoop();
	seg->seg.ps = ps;
	seg->seg.pe = pe;
	seg->seg.bArc = false;
	seg->bSingle = false;
	seg->ptInters.clear();
	seg->id = g_idSeg;

	g_Func->m_idToSegMap.insert(g_idSeg, seg);
	g_Func->m_Segs.push_back(seg);
}

void FuncGetLoops::DoFindLoop()
{
	g_Func->GetAllSegsInterPoint();
	g_Func->GetAllIntLoops();
}

void FuncGetLoops::GetResultAndClose(std::vector<loopResult> &lps)
{
	lps = g_Func->m_intLoops;

	delete g_Func;
}

// 2，计算每个线段上的所有交点,去掉胡子，由交点可以得到相关线段
void FuncGetLoops::GetAllSegsInterPoint()
{
	std::vector<LineSegForLoop*> SegsNew;

	bool bVer = false;
	size_t len = m_Segs.size();
	for (size_t i = 0; i < len; i++)
	{
		bVer = IsSegVer(m_Segs[i]);

		// 计算每个线段上的所有交点
		for (size_t j = i + 1; j < len; j++)
		{
			double param = -1;

			DPoint3d ptInter;
			if (GeMathPublic::isSegInterSeg(m_Segs[i]->seg.ps, m_Segs[i]->seg.pe, m_Segs[j]->seg.ps, m_Segs[j]->seg.pe, ptInter, param))
			{
				if (param != -1)
				{
					SegInterPoint inter;
					inter.pt = ptInter;

					AddInterPointToSeg(bVer, m_Segs[i], inter, m_Segs[j]->id);

					bool bVerJ = IsSegVer(m_Segs[j]);
					AddInterPointToSeg(bVerJ, m_Segs[j], inter, m_Segs[i]->id);
				}
			}
		}

		// 不要胡子线段
		ClearSingleSeg(m_Segs[i], SegsNew, false);
	}

	for (auto& seg : SegsNew)
	{
		int kkk = 0;
	}

	m_Segs.clear();
	m_Segs = SegsNew; // 此时仍然有可能有胡子

	SegsNew.clear();
	for (auto& seg : m_Segs)
	{
		ClearSingleSeg(seg, SegsNew, true);
	}

	m_Segs.clear();
	m_Segs = SegsNew;

	for (auto& seg : m_Segs)
	{
		int kkk = 0;
	}

	for (auto& segmini : m_ChildSegs)
	{
		int kkk = 0;
	}

	LineSegForLoop* seg1;
	if (m_idToSegMap.getAt(1, seg1))
	{
		int kkk = 0;
	}
}

void FuncGetLoops::ClearSingleSeg(LineSegForLoop* seg, std::vector<LineSegForLoop*> &SegsNew, bool bAddMiniSeg)
{
	// 将不是胡子的Seg 添加到 SegsNew
	// 去掉胡子
	if (seg->ptInters.size() > 1)
	{
		bool bSingle = IsSegSingleByJoinedSegs(seg);
		seg->bSingle = bSingle;
		if (!bSingle)
		{
			if (bAddMiniSeg) AppendChildSegsFromSeg(seg);
			SegsNew.push_back(seg);
		}
	}
	else
	{
		seg->bSingle = TRUE;
	}
}

bool FuncGetLoops::IsSegSingleByJoinedSegs(LineSegForLoop* seg)
{
	// 如果交点对应的线段 是胡子，那本线段也是胡子
	for (auto& inter : seg->ptInters)
	{
		for (auto& id : inter.idJoinedSegs)
		{
			LineSegForLoop* seg2;
			if (!m_idToSegMap.getAt(id, seg2)) return false;
			if (!seg2->bSingle)
			{
				return false;
			}
		}
	}

	return true;
}

// 3,生成离散化的线段集合
bool FuncGetLoops::AppendChildSegsFromSeg(LineSegForLoop* seg)
{
	// 按照和起点距离 将所有交点进行排序
	SortSegInterPoints(seg);

	seg->idChilds.clear();

	// 不需要起始终止点，保证 childSeg 不是胡子
	size_t len = seg->ptInters.size();
	for (size_t i = 0; i < len - 1; i++)
	{
		MiniLineSegForLoop* minSeg = new MiniLineSegForLoop();

		minSeg->ps = seg->ptInters[i];
		minSeg->pe = seg->ptInters[i + 1];

		minSeg->bArc = seg->seg.bArc;
		minSeg->pc = seg->seg.pc;

		minSeg->id = seg->id;
		minSeg->idchild = ++g_idChildSeg;
		minSeg->bHasEToS = false;
		minSeg->bHasSToE = false;

		m_ChildSegs.push_back(minSeg);

		seg->idChilds.push_back(minSeg->idchild);

		m_idToSMiniSegMap.insert(g_idChildSeg, minSeg, false);
	}

	return true;
}

bool FuncGetLoops::GetNoClosedMiniSeg(int& idChild)
{
	// 获取还没有围合的子线段
	for (auto& childseg : m_ChildSegs)
	{
		if ((!childseg->bHasEToS)&&(!childseg->bHasSToE))
		{
			idChild = childseg->idchild;

			return true;
		}
	}

	return false;
}

void FuncGetLoops::GetAllIntLoops()
{
	int idChild = 0;
	while (GetNoClosedMiniSeg(idChild))
	{
		MiniLineSegForLoop* seg;
		if (m_idToSMiniSegMap.getAt(idChild,seg))
		{
			GetLoopFromMiniSegDoubleWay(seg);
		}
	}
}

void FuncGetLoops::GetLoopFromMiniSegDoubleWay(MiniLineSegForLoop* seg)
{
	// 从两个方向进行围合

	if (seg->id == 3)
	{
		int kkk = 0;
	}
	loopResult lp;
	if (GetLoopFromStartMiniSeg(seg, lp, true))
	{
		lp.isChildLoop = true;
		m_intLoops.push_back(lp);
	}

	loopResult lp2;
	if (GetLoopFromStartMiniSeg(seg, lp2, false))
	{
		lp2.isChildLoop = true;
		m_intLoops.push_back(lp2);
	}
}

// 从一个离散线段围合一个子环
bool FuncGetLoops::GetLoopFromStartMiniSeg(MiniLineSegForLoop* seg, loopResult& lp, bool bSToE)
{
	// 如果围合成功，需要设置围合半边信息
	// 围合 最小轮廓，设置边的半边属性，单方向 或 正反两方向
	DPoint3d startPoint = seg->ps.pt,endPoint;

	if (!bSToE) startPoint = seg->pe.pt;

	DPoint3d ps0 = startPoint;

	lp.m_ChildSegIds.clear();

	MiniSegLoopUnit lpUnit;

	UINT32 idnex = 0;
	UINT32 idstart = seg->idchild;
	UINT32 idcur = idstart;

	double A = 0;

	vector<DPoint3d> plPts;

	plPts.push_back(startPoint);

	bool bClosed = false;
	while (TRUE)
	{
		bool bStart = false;

		if (GetNextMiniSeg(idcur, startPoint, endPoint, bStart, idnex))
		{
			lpUnit.idchild = idcur;
			lpUnit.bS_E = bStart;  // 记录这个的目的，是确定离散SEG的半边，如果只有一个方向，是用于围合外轮廓的边

			lpUnit.resultSeg.ps = startPoint;
			lpUnit.resultSeg.pe = endPoint;
			lpUnit.resultSeg.bArc = false;

			//A += (startPoint.x*endPoint.y) - (endPoint.x*startPoint.y);

			lp.m_ChildSegIds.push_back(lpUnit);

			if (idnex != idstart) plPts.push_back(endPoint);
			if (idnex == idstart)
			{
				bClosed = true;

				bool bAnti = IsPolyAntiWise(plPts);

				if (bAnti)
				{
					int kkk = 0;
				}
				else
				{
					// 围合的内环不是逆时针，是外环暂时无效处理，因为此处只处理内环的围合，一定按逆时针进行围合内环
					bClosed = false;
					return false;
				}

				break;
			}

			// 准备从下一段开始，寻找
			idcur = idnex;
			startPoint = endPoint;
			idnex = -1;
		}
		else
		{
			// 即使没有围合，也应该设置半边信息，保证围合过的线段，不再进行围合新的LOOP
			bClosed = false;
			break;
		}
	}

	// 设置各子段的半边
	SetLoopSegsHalfSide(lp);

	return bClosed;
}

bool FuncGetLoops::IsPolyAntiWise(vector<DPoint3d> polygon)
{
	int i, index;
	DPoint3d a, b, v;
	v = polygon[0];
	int vcount = polygon.size();
	index = 0;
	for (i = 1; i<vcount; i++) // 找到最低且最左顶点，肯定是凸顶点 
	{
		if (polygon[i].y<v.y || polygon[i].y == v.y && polygon[i].x<v.x)
		{
			index = i;
		}
	}
	v = polygon[index];
	a = polygon[(index - 1 + vcount) % vcount]; // 顶点v的前一顶点 
	b = polygon[(index + 1) % vcount]; // 顶点v的后一顶点 

	double dd = GeMathPublic::multiply(v, b, a);
	return dd>0;
}

// 围合成功后，设置子环的半边属性
void FuncGetLoops::SetLoopSegsHalfSide(loopResult lp)
{
	for (auto& segId : lp.m_ChildSegIds)
	{
		MiniLineSegForLoop* seg;
		if (m_idToSMiniSegMap.getAt(segId.idchild,seg))
		{
			if (segId.bS_E)
			{
				seg->bHasSToE = true;
			}
			else
			{
				seg->bHasEToS = true;
			}
		}
	}
}

bool FuncGetLoops::IsPointStart(DPoint3d ps, UINT32 idChild,DPoint3d& ptOther)
{
	MiniLineSegForLoop* seg;
	if (m_idToSMiniSegMap.getAt(idChild,seg))
	//if (seg != NULL)
	{
		if (GeMathPublic::equal_point(ps, seg->ps.pt))
		{
			ptOther = seg->pe.pt;
			return true;
		}
	}

	ptOther = seg->ps.pt;
	return false;
}

// 围合的关键，获取 LOOP 的下一段合法子线段
bool FuncGetLoops::GetNextMiniSeg(UINT32 idseg, DPoint3d startPoint, DPoint3d& nexPoint, bool& bStart, UINT32& idsegnex)
{
	idsegnex = -1;  // 执行结束如果为 -1 ，表示没有找到

	if (idseg == 5)
	{
		int kkk=0;
	}

	MiniLineSegForLoop* seg; 
	if (!m_idToSMiniSegMap.getAt(idseg, seg)) return false;

	std::vector<UINT32> idsJoined;
	if (GeMathPublic::equal_point(startPoint, seg->ps.pt))
	{
		bStart = true;
		nexPoint = seg->pe.pt;
		idsJoined = seg->pe.idJoinedSegs;
	}
	else
	{
		bStart = false;
		nexPoint = seg->ps.pt;
		idsJoined = seg->ps.idJoinedSegs;
	}

	// 遍历pe上的所有原始线段，取逆时针夹角最小的 idSeg 进行围合
	double angTurnRightMin = -2*PI;
	double angTurnRight = 0;
	for (auto& idSeg : idsJoined)
	{
		// idSeg 是与主原始线段，相交的其他原始线段的 ID
		LineSegForLoop* seg;
		if (m_idToSegMap.getAt(idSeg,seg))
		{
			for (auto& idChild : seg->idChilds)
			{
				MiniLineSegForLoop* pMiniseg; 
				if (m_idToSMiniSegMap.getAt(idChild,pMiniseg))
				{
					BOOL bJoinedChildSeg = FALSE;
					DPoint3d pnex2;
					if (GeMathPublic::equal_point(nexPoint, pMiniseg->ps.pt))
					{
						bJoinedChildSeg = TRUE;
						pnex2 = pMiniseg->pe.pt;
					}
					else if (GeMathPublic::equal_point(nexPoint, pMiniseg->pe.pt))
					{
						bJoinedChildSeg = TRUE;
						pnex2 = pMiniseg->ps.pt;
					}

					if (bJoinedChildSeg)
					{
						angTurnRight = GetTurnRightAng(startPoint, nexPoint, pnex2);

						if (angTurnRight > angTurnRightMin)
						{
							angTurnRightMin = angTurnRight;
							idsegnex = idChild;
						}
					}
				}
			}
		}
	}

	// 1，根据首段方向； 2，获取终点处的所有子线段； 3，选择最靠右边的线段围合，即为顺时针围合最小内环

	if (idsegnex == -1) return false;
	return true;
}

// 如何计算两个子 Seg 的夹角
double FuncGetLoops::GetTurnRightAng(DPoint3d p1, DPoint3d inter, DPoint3d p2)
{
	const double epsilon = 1.0e-6; 
	const double nyPI = acos(-1.0); 

	double x1 = p1.x - inter.x;
	double y1 = p1.y - inter.y;
	double x2 = p2.x - inter.x;
	double y2 = p2.y - inter.y;

	double dist, dot, degree, angle;   
	// normalize  
	dist = sqrt( x1 * x1 + y1 * y1 ); 
	x1 /= dist; 
	y1 /= dist;  

	dist = sqrt( x2 * x2 + y2 * y2 ); 
	x2 /= dist; 
	y2 /= dist; 

	// dot product 
	dot = x1*x2 + y1*y2;
	if (fabs(dot - 1.0) <= epsilon)
		angle = 0.0;
	else if (fabs(dot + 1.0) <= epsilon) 
		angle = nyPI;
	else
	{
		double cross;
		angle = acos(dot);

		// cross product 
		cross = x1*y2 - x2*y1;

		// vector p2 is clockwise from vector p1  
		// with respect to the origin (0.0) 
		if (cross < 0)
		{
			angle = 2 * nyPI - angle;
		}
	}  

	degree = angle * 180.0 / nyPI; 

	return degree;

	//GeMathPublic::LINESEG l1,l2;
	//l1.s.x = inter.x;
	//l1.s.y = inter.y;
	//l1.e.x = p1.x;
	//l1.e.y = p1.y;

	//l2.s.x = inter.x;
	//l2.s.y = inter.y;
	//l2.e.x = p2.x;
	//l2.e.y = p2.y;

	//double a = (x1*x2+y1*y2)/sqrt((x1*x1 + y1*y1) * (x2*x2 + y2*y2));

	//double ang = acos(a);

	//double angj = lsangle(l1, l2);
	//if (angj < 0)
	//{
	//	angj = 2 * PI + angj;
	//}

	return 0;
	//DVec3d vec1 = DVec3d::FromStartEnd(p1, inter);
	//DVec3d vec2 = DVec3d::FromStartEnd(inter, p2);

	//return vec2.AngleToXY(vec1);
}

bool FuncGetLoops::IsSegVer(LineSegForLoop* seg)
{
	return (fabs(seg->seg.ps.x - seg->seg.pe.x) < fabs(seg->seg.ps.y - seg->seg.pe.y));
}

// 设置交点的关联线段
void FuncGetLoops::AddInterPointToSeg(bool bVer, LineSegForLoop* seg, SegInterPoint inter, UINT32 idOther)
{
	if (bVer)
	{
		inter.disToStart = inter.pt.y - seg->seg.ps.y;
	}
	else
	{
		inter.disToStart = inter.pt.x - seg->seg.ps.x;
	}

	BOOL bHas = FALSE;
	size_t len = seg->ptInters.size();
	for (size_t i = 0; i < len; i++)
	{
		if (fabs(seg->ptInters[i].disToStart - inter.disToStart)<0.01)
		{
			bHas = TRUE;
			seg->ptInters[i].idJoinedSegs.push_back(idOther);
			return;
		}
	}

	if (!bHas)
	{
		inter.ids = seg->id;
		inter.idJoinedSegs.clear();
		inter.idJoinedSegs.push_back(idOther);
		seg->ptInters.push_back(inter);
	}
}

void FuncGetLoops::SortSegInterPoints(LineSegForLoop* seg)
{
	std::sort(seg->ptInters.begin(), seg->ptInters.end());
}

void FuncGetLoops::CloseOutLoop()
{
}
